package basic.study.algorithms.solution.DynamicProgramming;

import java.util.ArrayList;

/**
 * @author Kevin
 * @date 2020/2/19 20:24
 * 求解最长递增子序列
 * 我们有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？
 * 比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，
 * 所以最长递增子序列的长度是 4。
 */
public class IncreSub {
    public int longestIncresingSubString(int[] arr) {
        if (arr.length < 2) return arr.length;
        int[] states = new int[arr.length];
        states[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            for (int j = i-1; j >= 0; j++) {
                if (arr[j] < arr[i]) {//如果i之前的数值j比i小
                    if(states[j] > max) {//j处于递增序列中
                        max = states[j];
                    }
                }
            }
            states[i] = max + 1;//即使i无法处于前序的递增序列中，也是1
        }
        int result = 0;
        for (int i = 0; i < states.length; i++) {
            if (states[i] > result) result = states[i];
        }
        return result;
    }
}
